package demo.DataStrucAndAlgo.Easy_pritice;

import java.util.*;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/9/4-09-04-16:47
 * @Description：demo.DataStrucAndAlgo.Easy_pritice
 */
public class zi_String {
    /*
    给定一个字符串s和一个字符串数组words。words中所有字符串 长度相同。s中的 串联子串 是指一个包含words中所有字符串以任意顺序排列连接起来的子串。

例如，如果words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"， 和"efcdab" 都是串联子串。"acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联字串在s中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。*/
    public static void main(String[] args) {
//        String s = "barfoothefoobarman";
//        String[] words = {"foo","bar"};
//        findSubString(s,words);
        System.out.println(findAnagrams("cbaebabacd", "abc"));
    }

    public static List<Integer> findAnagrams(String s, String p) {
        if(s.length()<p.length()){
            return new ArrayList<Integer>();
        }
        int a[] = new int[26];     //p
        int b[] = new int[26];     //s
        List<Integer> result = new ArrayList();
        for(int i = 0 ; i < s.length()-p.length()+1; i++ ){
            for(int j = i; j < p.length()+i; j++){
                if(i > 0){
                    b[s.charAt(j-1)-'a']--;
                    System.out.println(j-1);
                }else{
                    a[p.charAt(j)-'a']++;
                }
                b[s.charAt(j)-'a']++;
                System.out.println(j);
            }
            if(Arrays.equals(a,b)){
                result.add(i);
            }
        }
        return result;
    }
    public static List<Integer> findSubString(String s, String[] words){
        int[] nums = null;
        System.out.println(nums.length);
        List<Integer> result = new ArrayList<>();
        Map<String, Integer> map1 = new HashMap<>();
        for (String word : words) {
            map1.put(word,map1.getOrDefault(word,0) + 1);   //s中是否出现过words
        }
        System.out.println(map1);
        int wordLen = words[0].length();
        int m = words.length;
        for(int i = 0; i < wordLen; i++){
            Map<String,Integer> map2 = new HashMap<>();
            int l = i,r = i,count = 0;
            while (r + wordLen <= s.length()){
                String w = s.substring(r,r+wordLen);
                r+= wordLen;
                if(!map1.containsKey(w)){
                    l = r;
                    count = 0;
                    map2.clear();
                }else{
                    map2.put(w,map2.getOrDefault(w,0)+1);
                    count++;
                    while(map2.get(w) > map1.get(w)){
                        String first = s.substring(l,l+wordLen);
                        count--;
                        map2.put(first,map2.getOrDefault(first,0)-1);
                        l += wordLen;
                    }
                    if(count == m){
                        result.add(l);
                        String first = s.substring(l,l+wordLen);
                        count--;
                        map2.put(first,map2.get(first)-1);
                        l += wordLen;
                    }
                }
            }
        }
        return result;
    }
}